With the ever-increasing spread of electronic communication and electronic identification there has been a corresponding increase in demand for cryptographic processes, where users require cryptographic processes to enable encryption of data for security purposes and/or for the purposes of providing identification.
Typically encryption keys are certified by trusted authorities and are disseminated using digital certificates where, to allow wide spread availability of cryptographic processes, a hierarchy of trusted authorities exist. Within a hierarchy of trusted authorities a root trusted authority issues a digital certificate relating to a private/public key to a second level trusted authority by using the root authority's private key to sign the second level's trusted authority's public key and thereby providing confirmation that the second level private key is authorized by the root authority. Correspondingly the second level trusted authority issues a digital certificate relating to a different private/public key to a third level trusted authority that is signed with the second level's private key and so forth. However, for a user to determine that the public key associated with the third level trusted authority is derived with the authority of the root trusted authority it is necessary for the user to trace the digital certificates that incorporated the various public keys.
It is desirable to improve this situation.
Embodiments of the present invention to be described hereinafter make use of cryptographic techniques using bilinear mappings. Accordingly, a brief description will now be given of certain such prior art techniques.
In the present specification, G1 and G2 denote two algebraic groups of prime order q in which the discrete logarithm problem is believed to be hard and for which there exists a computable bilinear map p, for example, a Tate pairing t or Weil pairing ê. Thus, for the Weil pairing:ê: G1×G1→G2 where G2 is a subgroup of a multiplicative group of a finite field. The Tate pairing can be similarly expressed though it is possible for it to be of asymmetric form:t: G1×G0→G2 where G0 is a further algebraic group the elements of which are not restricted to being of order q. Generally, the elements of the groups G0 and G1 are points on an elliptic curve though this is not necessarily the case.
As is well known to persons skilled in the art, for cryptographic purposes, a modified form of the Weil pairing is used that ensure p (P, P) ≠1 where PεG1; however, for convenience, the pairing is referred to below simply by its usual name without labeling it as modified. Further background regarding Weil and Tate pairings and their cryptographic uses can be found in the following references:                G. Frey, M. Müller, and H. Rück. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Transactions on Information Theory, 45(5):1717-1719, 1999.        D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. In Advances in Cryptology—CRYPTO 2001, LNCS 2139, pp. 213-229, Springer-Verlag, 2001.        
For convenience, the examples given below assume the use of a symmetric bilinear map (p:G1×G1→G2) with the elements of G1 being points on an elliptic curve; however, these particularities, are not to be taken as limitations on the scope of the present invention.
As the mapping between G1 and G2 is bilinear exponents/multipliers can be moved around.
For example if a, b, cεFq and P, QεG1 then
                                          t            ⁡                          (                              aP                ,                bQ                            )                                c                =                                            t              ⁡                              (                                  aP                  ,                  cQ                                )                                      b                    =                                                    t                ⁡                                  (                                      bP                    ,                    cQ                                    )                                            a                        =                                                            t                  ⁡                                      (                                          bP                      ,                      aQ                                        )                                                  c                            =                                                                    t                    ⁡                                          (                                              cP                        ,                        aQ                                            )                                                        b                                =                                                      t                    ⁡                                          (                                              cP                        ,                        bQ                                            )                                                        a                                                                                            =                                            t              ⁡                              (                                  abP                  ,                  Q                                )                                      c                    =                                    t              ⁡                              (                                  abP                  ,                  cQ                                )                                      =                                                            t                  ⁡                                      (                                          P                      ,                      abQ                                        )                                                  c                            =                              t                ⁡                                  (                                      cP                    ,                    abQ                                    )                                                                                            =        …                                =                              t            ⁡                          (                              abcP                ,                Q                            )                                =                                    t              ⁡                              (                                  P                  ,                  abcQ                                )                                      =                                          t                ⁡                                  (                                      P                    ,                    Q                                    )                                            abc                                          
Additionally, the following cryptographic hash functions are defined:H1: {0,1}*→G1 H2: {0,1}*→Fq H3: G2→{0,1}*
A normal public/private key pair can be defined for a trusted authority:                the private key is s where sεFq         the public key is (P,R) where PεG1 and RεG1, with R=sP        
Additionally, an identifier based public key/private key pair can be defined for a party with the cooperation of the trusted authority. As is well known to persons skilled in the art, in “identifier-based” cryptographic methods a public, cryptographically unconstrained, string is used in conjunction with public data of a trusted authority to carry out tasks such as data encryption or signing. The complementary tasks, such as decryption and signature verification, require the involvement of the trusted authority to carry out computation based on the public string and its own private data. Frequently, the string serves to “identify” the intended message recipient and this has given rise to the use of the label “identifier-based” or “identity-based” generally for these cryptographic methods. However, depending on the application to which such a cryptographic method is put, the string may serve a different purpose to that of identifying the intended recipient and, indeed, may be an arbitrary string having no other purpose than to form the basis of the cryptographic processes.
Accordingly, the use of the term “identifier-based” herein in relation to cryptographic methods and systems is to be understood simply as implying that the methods and systems are based on the use of a cryptographically unconstrained string whether or not the string serves to identify the intended recipient. Furthermore, as used herein the term “string” is simply intended to imply an ordered series of bits whether derived from a character string, a serialized image bit map, a digitized sound signal, or any other data source.
In the present case, the identifier-based public/private key pair defined for the party has a public key QID and private key SID where QID, SIDεG1. The trusted authority's normal public/private key pair (P,R/s) is linked with the identifier-based public/private key bySID=sQID and QID=H1(ID)where ID is the identifier string for the party.
Some typical uses for the above described key pairs will now be given with reference to FIG. 1 of the accompanying drawings that depicts a trusted authority 10 with a public key (P, sP) and a private key s. A party A serves as a general third party whilst for the identifier-based cryptographic tasks (IBC) described, a party B has an IBC public key QID and an IBC private key SID.
Standard Signatures (See Dashed Box 2): The holder of the private keys (that is, the trusted authority 1 or anyone to whom the latter has disclosed s) can use s to sign a bit string; more particularly, where m denotes a message to be signed, the holder of s computes:V=sH1(m).
Verification by party A involves this party checking that the following equation is satisfied:t(P, V)=t(R, H1(m))
This is based upon the mapping between G1 and G2 being bilinear exponents/multipliers, as described above. That is to say,
                              t          ⁡                      (                          P              ,              V                        )                          =                  t          ⁡                      (                          P              ,                                                sH                  1                                ⁡                                  (                  m                  )                                                      )                                                  =                              t            ⁡                          (                              P                ,                                                      H                    1                                    ⁡                                      (                    m                    )                                                              )                                s                                        =                  t          ⁡                      (                          sP              ,                                                H                  1                                ⁡                                  (                  m                  )                                                      )                                                  =                  t          ⁡                      (                          R              ,                                                H                  1                                ⁡                                  (                  m                  )                                                      )                              
Identifier-Based Encryption (See Dashed Box 3):—Identifier based encryption allows the holder of the private key SID of an identifier based key pair (in this case, party B) to decrypt a message sent to them encrypted (by party A) using B's public key QID.
More particularly, party A, in order to encrypt a message m, first computes:U=rPwhere r is a random element of Fq. Next, party A computes:V=m{circle around (+)}H3(t(R, rQID))
Party A now has the ciphertext elements U and V which it sends to party B.
Decryption of the message by party B is performed by computing:
                              V          ⊕                      H3            ⁡                          (                              t                ⁡                                  (                                      U                    ,                                          S                      ID                                                        )                                            )                                      =                  V          ⊕                                    H              3                        ⁡                          (                              t                ⁡                                  (                                      rP                    ,                                          sQ                      ID                                                        )                                            )                                                              =                  V          ⊕                                    H              3                        ⁡                          (                                                t                  ⁡                                      (                                          P                      ,                                              Q                        ID                                                              )                                                  rs                            )                                                              =                  V          ⊕                                    H              3                        ⁡                          (                              t                ⁡                                  (                                      sP                    ,                                          rQ                      ID                                                        )                                            )                                                              =                  V          ⊕                                    H              3                        ⁡                          (                              t                ⁡                                  (                                      R                    ,                                          rQ                      ID                                                        )                                            )                                                              =        m            
Identifier-Based Signatures (See Dashed Box 4):—Identifier based signatures using Tate pairing can be implemented. For example:
Party B first computes:r=t(SID, P)k where k is a random element of Fq.
Party B then apply the hash function H2 to m∥r (concatenation of m and r) to obtain:h=H2(m∥r).
Thereafter party B computesU=(k−h)SID thus generating the output U and h as the signature on the message m.
Verification of the signature by party A can be established by computing:r′=t(U, P)·t(QID, R)h where the signature can only be accepted if h=H2 (m∥r′).
It will be recalled that the problem discussed at the outset was how a third party could verify the associations between trusted authorities arranged in a hierarchy without having to follow a trail of certificates. In fact, the above-described IBC encryption/decryption method offers one possible solution. Consider the situation where a trusted authority at one level in the hierarchy has an IBC public key QID/private key SID pair with the private key being provided by a trusted authority in the next level up on the basis of the ID of the lower-level trusted authority and the private key s of a normal public key (P, sP)/private key s pair held by the higher-level trusted authority. A third party could then check that the lower-level trusted authority was associated with the higher level one by an IBC-based challenge/response mechanism. More particularly, the third party could encrypt a nonce (random number) using both the public key element sP of the higher-level trusted authority and the IBC public key QID of the lower-level trusted authority. The third party sends the encrypted nonce to the lower-level trusted authority and asks it to decrypt and return the nonce—the lower-level trusted authority will only be able to do this if it has (or can get) the key SID(=sQID) from the higher-level trusted authority. Thus, if the lower-level trusted authority can return the decrypted nonce, the association between the lower-level trusted authority and the higher level trusted authority is proved. Whilst this approach is viable, it involves an exchange of messages between the third party and the lower-level trusted authority and also (if the lower-level trusted authority does not already have its IBC private key) between the lower-level trusted authority and the higher-level trusted authority. In many situation this may either not be possible or undesirable—for example, the third party may wish to check the association between the trusted authorities offline or the third party may not wish to let it be known that it is carrying out the check.
It is an object of the present invention to provide a way of checking the association between two parties that obviates at least some of the difficulties noted above.